package com.code.leetcode._202508;
//69 x的平方根
public class MySqrt {
    /**给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
     示例1：输入：x = 4
     输出：2
     示例2：输入：x = 8
     输出：2
     解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。**/
    public static void main(String[] args) {
        MySqrt m = new MySqrt();
        System.out.println(m.mySqrt(8));
    }
    /**袖珍计算器算法
     * 本题是一道常见的面试题，面试官一般会要求面试者在不使用根号x函数的情况下，得到 x 的平方根的整数部分。一般的思路会有以下几种：
     1、通过其它的数学函数代替平方根函数得到精确结果，取整数部分作为答案；
     2、通过数学方法得到近似结果，直接作为答案。
     「袖珍计算器算法」是一种用指数函数 exp 和对数函数 ln 代替平方根函数的方法。我们通过有限的可以使用的数学函数，得到我们想要计算的结果。
     我们将根号x写成幂的形式x的1/2次幂，再使用自然对数 e 进行换底，即可得到这样我们就可以得到根号x的值了
     **/
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = (int) Math.exp(0.5 * Math.log(x));
        return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }
    /**二分查找
     * 由于 x 平方根的整数部分 ans 是满足 k的平方≤x 的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案。
     * 二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素 mid 的平方与 x 的大小关系，
     * 并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算，不会存在误差，因此在得到最终的答案 ans 后，也就不需要再去尝试 ans+1 了。
     ***/
    public int mySqrt1(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
    /**牛顿迭代**/
    public int mySqrt2(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return (int) x0;
    }
}
